#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int x, y;
    cin >> x >> y;
    int GCD = gcd(x, y);
    int AND = x & y;
    int XOR = x ^ y;
    if (!XOR || !AND) cout << 1 << endl;
    else if (!(AND ^ x) || !(AND ^ y) || !(XOR & x) || !(XOR & y) || !(GCD ^ x) || !(GCD ^ y)
        || !(GCD & x) || !(GCD & y))
        cout << 2 << endl;
    else cout << 3 << endl;

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}